Most digital electronic systems, such as used in computers, microprocessors, and controllers, generally employ some means for synchronizing various transitions which occur during digital processing. Typically, the synchronization is provided using a clock signal which acts as a trigger allowing various transitions from one state to another state to occur. In most synchronous sequential machines the clock signal controls data movement in the machine, thus providing sufficient time for various subcircuits to respond and achieve the desired values prior to beginning the next processing step. The triggering action of the clock provides an inherent filtering mechanism since logic noise (glitches) are not sensed by the next stage unless the noise occurs at or near the time that the clock signal triggers the digital system to transition onto the next state. The synchronization and filtering aspects of clock driven digital systems have in part been responsible for allowing large digital systems to be designed and implemented by simplifying the electronic engineering required to produce operable systems.
Despite their advantages, clock driven digital systems do suffer limitations. The frequency of the system clock must necessarily be slow enough so that all clocked components of the system can achieve proper logic stability between clock triggering intervals. This requirement causes the loss of valuable time since one component say respond more quickly than another. The reaction time of the slowest component dictates the maximum acceptable operating frequency used by the system. Thus the overall operating speed is decreased by delays which occur along the critical timing paths for each electronic stage which respond faster than the duration of the clock interval.
Another difficulty associated with synchronous or clock driven digital systems is the potential for clock distribution problems called clock skew. Clock skew occurs when complex digital systems are operated at a clock frequency too high for the individual components of the system to operate synchronously. Multiple clocked systems are particularly vulnerable to clock distribution problems. In general, the higher the clock frequency the more difficult it is to synchronize the various clocked components of a complex digital system.
Because of the problems discussed above and other difficulties, it is desirable in some applications to employ asynchronous or clock independent digital systems. Asynchronous sequential digital systems do not require a periodic triggering signal (clock) to coordinate the controller and data path. Such asynchronous sequential systems have the inherent advantage of operating without clock holdup time delay since the various components of the system do not have to wait for a clock triggering signal before proceeding on to the next step. Accordingly, asynchronous sequential systems have the potential for higher operating speeds with fewer clock distribution problems.
A number of timing defects unique to asynchronous sequential machines have prevented widespread development of these machines. One important type of timing defect is termed a race condition. A race condition exists when an asynchronous sequential machine can take two or more alternative paths to the same stable. In general, a race condition is not a severe problem unless output race glitches are produced. Even then the problem may not be disruptive to the operation of the sequential machine. Critical races, on the other hand, must never be permitted to exist. Critical races can occur when two or more alternative paths in a transition can lead to two or more distinct stable states. In such instances the destination state is not predictable and malfunction of the sequential machine is highly probable.
An endless cycle (oscillation) is another type of timing defect that can exist in asynchronous sequential machines. If present, an endless cycle is certain to cause the sequential machine to malfunction.
Asynchronous sequential machines also suffer substantially more problems than synchronous designs due to the presence of various types of hazards. Hazards are herein defined as unwanted logic level transients or error transitions. Static hazards, for example, can be identified and eliminated by means of combinational logic and, therefore, do not constitute a serious problem. Essential hazards, on the other hand, pose a very serious threat to successful operation of asynchronous sequential machines which operate in the fundamental mode, and these timing defects cannot be detected or eliminated by combinational logic means as can static hazards. If even one single essential hazard is active in a given asynchronous sequential machine and steps are not taken to eliminate it, the essential hazard will cause the machine to malfunction. Essential hazards can be eliminated only be placing delays on feedback lines and this slows down circuit response. More than any other timing defect, essential hazards are responsible for a general opinion among digital design engineers that asynchronous sequential machines are too complex and too unreliable to be of serious commercial interest.
The elimination of all the above potential problems in a complex asynchronous sequential system can be a formidable task requiring exhaustive analyses by digital electronic designers. The greater potential for defects of the types mentioned above to exist in asynchronous sequential machines, compared to their synchronous machine counterparts, has slowed progress in this technological area and has substantially increased developmental costs of asynchronous sequential systems. There remains a great need for development of asynchronous sequential machine technology so as to meet the needs of a next generation of microprocessors and computers which will be very complex and which will be operated at speeds in excess of those possible in a clock driven environment. Many digital design experts agree that the synchronous machine concept has already been pushed to its practical limit.
This application describes an invention which alleviates or solves at least some of the problems discussed above. The invention is programmable and includes one or more modules which can be cascaded to extend the number of control states. The programmability and expandability make devices according to the invention highly versatile and easily adaptable to a wide variety of applications. It is believed that the invention disclosed in this application will set new standards for sequential machine speed, compactness and reliability.